package com.alogic.validator.impl.pwd;

import com.alogic.validator.impl.Similar;
import com.anysoft.util.Properties;
import com.anysoft.util.PropertiesConstants;
import org.apache.commons.lang3.StringUtils;

/**
 * 根据Levenshtein距离判断相似性
 *
 * @since 1.6.13.28 [20201218 duanyy] <br>
 */
public class Levenshtein extends Similar {
    protected double threshold = 0.5f;

    @Override
    public void configure(Properties p) {
        super.configure(p);
        threshold = PropertiesConstants.getDouble(p,"threshold",0.5f,true);
    }

    @Override
    protected boolean isSimilar(String key, String value) {
        return levenshtein(key,value) > threshold;
    }

    public static float levenshtein(String a, String b) {
        if (StringUtils.isEmpty(a) && StringUtils.isEmpty(b)) {
            return 1f;
        }
        if (StringUtils.isEmpty(a) && StringUtils.isEmpty(b)) {
            return 0f;
        }
        int editDistance = editDis(a, b);
        return 1 - ((float) editDistance / Math.max(a.length(), b.length()));
    }

    private static int editDis(String a, String b) {
        int aLen = a.length();
        int bLen = b.length();

        if (aLen == 0) return aLen;
        if (bLen == 0) return bLen;

        int[][] v = new int[aLen + 1][bLen + 1];
        for (int i = 0; i <= aLen; ++i) {
            for (int j = 0; j <= bLen; ++j) {
                if (i == 0) {
                    v[i][j] = j;
                } else if (j == 0) {
                    v[i][j] = i;
                } else if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    v[i][j] = v[i - 1][j - 1];
                } else {
                    v[i][j] = 1 + Math.min(v[i - 1][j - 1], Math.min(v[i][j - 1], v[i - 1][j]));
                }
            }
        }
        return v[aLen][bLen];
    }
}